package q769_maxChunksToSorted;

import java.util.Deque;
import java.util.LinkedList;

public class Solution_3 {
    /*
    单调栈的非典型用例：
    维护递增的单调栈
    遍历每一个元素，如果当前元素大于栈顶元素说明找到了一个新的分段
    如果当前元素小于栈顶元素，保存栈顶元素，然后将大于当前元素的所有元素出栈后，将之前保存的栈顶元素压入栈中，代表了一个分段。
    最后返回栈中元素的个数即可
    即每一段的 最大值 代表了当前段

    首先栈中存的元素是 下标

    下标： 0 1 2 | 3 4 | 5 6 7
    元素： 2 1 0 | 4 3 | 7 6 5
    首先栈在 2 1 0这一段会不断使2进出栈 到4时 则会进栈4 到3时 则使4出栈 然后看栈中是否有比当前arr[i]大的 之前的段的代表
    如果有 则说明之前的一段是无效的 所以要将其出栈 在此题中则由于3 > 2所以不出栈
    因此后面的也按照该条件
     */
    public int maxChunksToSorted(int[] arr) {
        Deque<Integer> stack = new LinkedList<>();
        stack.addLast(0);

        for (int i = 1; i < arr.length; i++) {
            if (arr[stack.peek()] < arr[i]) {
                stack.push(i);
                continue;
            }

            int max = stack.peek();

            while (!stack.isEmpty() && arr[stack.peek()] > arr[i]) {
                stack.pop();
            }

            stack.push(max);
        }

        return stack.size();
    }
}

